public class GCF {
    public static int BF(int m, int n) {
        for (int i = Math.min(m, n); i > 0; i--) {
            if (m % i == 0 && n % i == 0) {
                return i;
            }
        }
        return 0;
    }

    public static int Euclid(int m, int n) {
        int max = Math.max(m, n);
        int min = Math.min(m, n);
        if (max % min == 0)
            return min;
        else {
            return Euclid(min, max % min);
        }
    }

    public static int MPRS(int m, int n) {
        int i = 0;
        while (m % 2 == 0 && n % 2 == 0) {
            m /= 2;
            n /= 2;
            i++;
        }

        int max = Math.max(m, n);
        int min = Math.min(m, n);

        while (min != (max - min)) {
            max = Math.max(min, max - min);
            min = Math.min(min, max - min);
        }

        if (i == 0) {
            return n;
        } else {
            return (1 << i) * n;
        }
    }

    public static int Stein(int m, int n) {
        if (m == 0)
            return n;
        if (n == 0)
            return m;

        int i = 1;
        while (m % 2 == 0 && n % 2 == 0) {
            i <<= 1;
            m >>= 1;
            n >>= 1;
        }
        while (m % 2 == 0) {
            m >>= 1;
        }
        while (n % 2 == 0) {
            n >>= 1;
        }

        return i * MPRS(m, n);
    }
}
